import math
import sys

class Heapsort:
    def __init__(self, A):
        self.A = A

    def max_heapify(self, i):

        global heapsize
        l = 2*i
        r = 2*i+1
        
        
        if l <= heapsize-1 and self.A[l] > self.A[i]:
            largest = l
            
        else:
            largest = i
            
        if r <= heapsize and self.A[r] > self.A[largest]:
            largest = r
            
        if largest != i:
            self.A[i], self.A[largest] = self.A[largest], self.A[i]
            self.max_heapify(largest)

    def build_max_heap(self):
        
        for i in reversed(range(0, (int(math.floor(len(self.A)/2))))):
            self.max_heapify(i)

    def heapsort(self):
        global heapsize
        heapsize = len(self.A)-1
        self.build_max_heap()
        for i in reversed(range(0, len(self.A))):
            self.A[0], self.A[i] = self.A[i], self.A[0]
            heapsize = heapsize - 1
            self.max_heapify(0)


